1. Field of the Invention
The present invention relates generally to the operation of multiple command queues and, more particularly, to queue ordering and execution with multiple interdependent queues.
2. Description of the Related Art
Within a variety of computer architectures, there are a variety of devices that utilize command queues. A command queue is memory device that stores execution commands. For example, Direct Memory Access (DMA) devices are notorious for utilizing command queues.
Typically, commands are forwarded to some device, such as a DMA device, for execution. However, due to system constraints, such as available communication channels, all the commands cannot be instantaneously and simultaneously executed. Instead, the commands are forwarded to a pipeline of the device for execution. The device then stores the commands in a command queue and eventually executes the commands.
There are a variety of manners to execute the command, which can vary. Two common methods of addressing the order of execution are to use strict ordering or to use stack down ordering. With strict ordering, commands are executed strictly on the order upon which the commands enter the command queue. For example, a store queue for a DMA module would likely use strict ordering. With stack down ordering, commands can, not only, be executed in the order in which the commands enter the command queue, but also from the middle of the queue. Stack down ordering is often desirable in situations where there is interdependency between commands in a given command queue. For example, a read command for a DMA module would likely use a stack down order.
Moreover, in a device that has a command queue, there may not necessarily be a single command queue. For example, a DMA module can have separate queues for both storing and reading. A problem can arise with the order of execution, though, if there are two or more queues. There can be cases where there is cross-dependency between commands of different command queues. In other words, there can be a first commands in one queue that requires execution of a second command in a second queue before execution of the first command. For example, in DMA device, if command 8 in the storage queue requires execution of command 4 in the read queue before the execution of command 8, then there is interdependency between the storage and the read queue.
In most cases, though, each command queue is distinct. In other words, each queue tracks the commands and executes each command according to the requirements within the queue. However, there are some cases where interdependencies between multiple queues exist. Typically, there is not an efficient technique or apparatus to track the order of execution and interdependencies across multiple queues.
Therefore, there is a need for a method and/or apparatus for tracking commands across multiple command queues that addresses at least some of the problems associated with convention methods and apparatuses associated with the operation of multiple command queues.